Boolean Algebra

What is it?

• Boolean algebra is the branch of algebra – a branch of mathematics that studies symbols and rules for manipulating them – where the values of the variables are truth values.
• Computers do these operations all the time. They are the basic building blocks of computation within computer programs.

Where does it come from and why is it important to us?

• Boolean algebra was developed by George Boole in his 1854 book titled An invesstigation of the Laws of Thought where he worked to formalize – to use symbolic notation with precise rules governing their manipulation – Aristotle’s system of logic.
• Claude Shannon – the inventor of information theory – utilized Boole’s ideas in his 1938 A Symbolic Analysis of Relay and Switching Circuits as the basis for designing and analyzing digital circuits.

Boolean algebra and “normal algebra”

There are lots of similarities between Boolean algebra and “normal algebra,” also called elementary algebra. You’re already familiar with algebra involving real numbers. In addition to arithmetic operations dealing with specific values, algebra introduces variables – or quantities without fixed values. The use of variables allows general relationships between quantities to be formally expressed.

Boolean algebra differs from elementary algebra in that expressions denote the truth values true and false. Computer scientists often represent these as bits or binary digits 1 and 0. However, Boolean values do not behave like the integers 1 and 0.

Be aware that Boolean values are not the same thing as binary numbers. The binary number system is an alternative notation for the real numbers. Boolean values, on the other hand, represent something entirely different from numbers.

Operations

There are three basic operations in Boolean algebra.

• AND (conjunction), denoted by $x \land y$ or $x \bullet y$. $x \land y = 1$ if $x = y = 1$ and $0$ otherwise.
• OR (disjunction), denoted by $x \lor y$ or $x + y$. $x \lor y = 0$ if $x = y = 0$ and 1 otherwise.
• NOT (negation), denoted by $\neg x$ or $\overline x$. This is a unary operation. $\neg x = 1$ if $x = 0$ and $\neg x = 0$ if $x = 1$.

These operations can be expressed by tabulating their values on a truth table as follows:

$x$	$y$	$x \land y$	$x \lor y$	$\neg x$
1	1	1	1	0
1	0	0	1	0
0	1	0	1	1
0	0	0	0	1

There are a number of secondary operations. Here are a few common ones.

• IF… THEN… (conditional), denoted by $x \to y$. It’s equivalent to $\neg x \lor y$
• XOR (exclusive or), denoted by $x \oplus y$. It’s equivalent to $(x \lor y) \land \neg (x \land y)$
• EQUIVALENCE (boolean equivalence), denoted by $x \equiv y$. It’s equivalen tto $\neg (x \oplus y)$

Here’s a truth table tabulating their results:

$x$	$y$	$x \to y$	$x \oplus y$	$x \equiv y$
1	1	1	0	1
1	0	0	1	0
0	1	1	1	0
0	0	1	0	1

Well formed Boolean expressions

Any variable is a wff (well formed formula), i.e. $x$
Any negated wff is a wff, i.e. $\neg x$
Any two wffs connected by a binary operation is a wff, i.e. $\neg x \lor y$

This is called a recursive definition.

Laws

A law of the Boolean algebra is an identity between two Boolean expressions. Here are some examples:

Associativity of OR: $x \lor (y \lor z) = (x \lor y) \lor z$
Associativity of AND: $x \land (y \land z) = (x \land y) \land z$
Commutativity of OR: $x \lor y = y \lor x$
Commutativity of AND: $x \land y = y \land x$
Distributivity of AND over OR: $x \land (y \lor z) = (x \land y) \lor (x \land z)$
Distributivity of OR over AND: $x \lor (y \land z) = (x \lor y) \land (x \lor z)$
Identity for OR: $x \lor 0 = x$
Identity for AND: $x \land 1 = x$
Contradiction: $x \land \neg x = 0$
Tautology: $x \lor \neg x = 1$
Absorption: $x \land (x \lor y) = x$
Absorption: $x \lor (x \land y) = x$
Double Negation: $\neg \neg x = x$
DeMorgans: $\neg x \land \neg y = \neg (x \lor y)$
DeMorgans: $\neg x \lor \neg y = \neg (x \land y)$

Practice

Let’s work out some problems on the Boolean algebra worksheet